class Solution:
    def perm(self, lst, l, left):
        if len(left) == 1:
            l.extend(left)
            lst.append(l)
            return
        for i in range(len(left)):
            temp_list = list(l)
            temp_left = list(left)
            temp_list.append(left[i])
            del temp_left[i]
            self.perm(lst, temp_list, temp_left)
    def permute(self, num):
        lst = []
        l = []
        self.perm(lst, l, num)
        return lst


num = 4
lst = range(1,num+1)
print lst
print ""
ss = Solution()
lst = ss.permute(lst)
for i in range(len(lst)):
    print lst[i]
print "%d permutations" % len(lst)
